/***********************************************************************
 ** Reykjavik University
 ** Grímur Tómasson & Eiríkur Fannar Torfason
 ** Copyright (c) 2011. All rights reserved.
 **
 ** This is an implementation of an iterative-deepening, alpha/beta 
 ** pruned MiniMax search. It lends itself well to time-bounded search
 ** scenarios (go deeper and deeper until the time limit is hit).
 ** This implementation also uses a 'killer move' heuristic to order
 ** moves.
 **
 **********************************************************************/

#include "IterativeDeepeningAlphaBetaSearchKillerMoves.h"

#include <limits.h>
#include <iostream>

#include "Common.h"
#include "Utility.h"

//----------------------------------------------------------------------------------------------------------
//Constants
const int PRIMARY_KILLER_MOVE = 0;
const int SECONDARY_KILLER_MOVE = 1;
const int NO_MOVE_FOUND = -1;

int (*ptr2UtilityFunction)(bitboard**, int*, int ) = 0;

//----------------------------------------------------------------------------------------------------------
//Declarations
int iterativeDeepeningAlphaBetaSearchKillerMoves_( bitboard* bitboardArrayPointer[], int* currentPlyPointer, 
												  int depthLimit, int& expanded, int& abort, int maxSearchDepth, int& bestMoveValue,
												  int lossOrWin[] );
int maxValueIDKM( bitboard* bitboardArrayPointer[], int* currentPlyPointer, int depthLimit, int& expanded, int alpha, int beta, int& abort, int maxSearchDepth );
int minValueIDKM( bitboard* bitboardArrayPointer[], int* currentPlyPointer, int depthLimit, int& expanded, int alpha, int beta, int& abort, int maxSearchDepth );

//----------------------------------------------------------------------------------------------------------

//
// Instead of trying the moves from left to right, we start in the middle and then back and forth with increasing
// distance.
//
const int searchPattern[] = {3,2,4,1,5,0,6};
//
// We'll keep track of two killer moves. We don't expect to go deeper than 25-plys.
//
int killerMoves[2][MAXIMUM_SEARCH_DEPTH];

void setKillerMove(int ply, int column)
{
	//
	// Is this move different from the current primary killer move at this level/ply?
	//
	if (killerMoves[PRIMARY_KILLER_MOVE][ply] != column)
	{
		//
		// Yup, demote the primary killer move and then make this our new primary killer move
		//
		killerMoves[SECONDARY_KILLER_MOVE][ply] = killerMoves[PRIMARY_KILLER_MOVE][ply];
		killerMoves[PRIMARY_KILLER_MOVE][ply] = column;
	}
}

void* iterativeDeepeningAlphaBetaSearchKillerMoves( void* idAlphaBetaParameters )
{
	IDAlphaBetaParameters* parameters = (IDAlphaBetaParameters*) idAlphaBetaParameters;
	
	ptr2UtilityFunction = parameters->ptr2UtilityFunction;
	
	//
	// Let's take stock of the current time so that we can later calculate the elapsed time
	//
	double millisecondsStart = getCurrTimeInMilliseconds();
	//
	// Declare (and initialize) variables
	//
	int bestMove = -1;
	int bestMoveValue = -1;
	int maxDepth;
	
	int lossOrWin[WIDTH]; //Loss or win found, score stored to diffrentiate
	
	for( int z = 0; z < WIDTH; ++z )
	{
		lossOrWin[z] = 0;
	}

	if( parameters->depthLimit_ > SIZE - (parameters->currentPly_ + 1 ) )
	{
		parameters->depthLimit_ = SIZE - (parameters->currentPly_ + 1 ); //The absolute maximum depth
	}
	
	//
	// Initialize the 'killer moves' array.
	//
	for( int i = 0; i < parameters->depthLimit_; ++i )
	{
		//
		// Try the central column first, then the second column
		//
		killerMoves[PRIMARY_KILLER_MOVE][i] = 3;
		killerMoves[SECONDARY_KILLER_MOVE][i] = 1;
	}
	//
	// Iterate, increasing the depth in each iteration of the loop 
	//
	for( maxDepth = 0; maxDepth <= parameters->depthLimit_; ++maxDepth )
	{
		//
		// Find the best move using the current depth limit
		//
		bestMove = iterativeDeepeningAlphaBetaSearchKillerMoves_( parameters->bitboardArray_, 
													  &parameters->currentPly_, 
													  maxDepth, 
													  parameters->expanded_,
													  parameters->abort_,
													  maxDepth,
													  bestMoveValue,
													  lossOrWin );
#ifdef OUTPUT_DEBUG_INFO
		std::cout << "Searched depth " << maxDepth << " limit: " << parameters->depthLimit_ << std::endl;
		std::cout << "Best move (this iteration): " << bestMove << ".  Utility: " << bestMoveValue << std::endl;
#endif
		//
		// Keep track of the best initial move
		// TODO: Ensure that level == 1 in the next ply (on Min's turn)
		//
		setKillerMove(0, bestMove);
		//
		// Update the elapsed time
		//
		double currentMilliseconds = getCurrTimeInMilliseconds();
		parameters->milliseconds_ += currentMilliseconds - millisecondsStart;
		millisecondsStart = currentMilliseconds;
		//
		// This has to be set iteratively since we don't know if we get to finish the next iteration
		//
		parameters->depthReached_ = maxDepth;

		if( bestMove == NO_MOVE_FOUND )  //At this point all moves lead to a loss
		{
			break;
		}
		if( bestMoveValue != INT_MIN )
		{
			parameters->bestMove_ = bestMove;
		}
		
		if( parameters->bestMove_ == -1 ) //To avoid returning -1 as a move in a certain loss
		{
			parameters->bestMove_ = firstLegalMove();
#ifdef OUTPUT_DEBUG_INFO	
			std::cout << "No legal move found, picking first legal one" << std::endl;
#endif
		}
		 

		if( bestMoveValue == INT_MAX )  //We have found a winning strategy, no need to search further
		{
			std::cout << "Winning strategy found, no more searching!" << std::endl;
			break;
		}
		
#ifdef OUTPUT_DEBUG_INFO
		std::cout << "Best move stored: " << parameters->bestMove_ << std::endl;
		std::cout << "Time so far: " << parameters->milliseconds_ << std::endl;
#endif
	}
	parameters->abort_ = 1; //Let the parent process know that searching is done.
	return 0;  //Null should not be used
}
//----------------------------------------------------------------------------------------------------------

int iterativeDeepeningAlphaBetaSearchKillerMoves_( bitboard* bitboardArrayPointer[], int* currentPlyPointer, int depthLimit, int& expanded, int& abort, int maxSearchDepth, int& bestMoveValue, int lossOrWin[]  )
{
	//
	// Declare (and initialize) variables
	//
	int bestMove = NO_MOVE_FOUND;
	bestMoveValue = INT_MIN;
	int value = INT_MIN;
	bitboard newBoard;
	int level = maxSearchDepth - depthLimit;
	int move = 0;
	//
	// Here we figure out which side is playing. We do this by looking at the current turn number. If it's an even
	// number then it's black's turn (side == 0), otherwise it's red's turn (side == 1). I guess we could use the
	// modulus operator but bitwise operators are simply more bad-ass.
	//
	int side = (*currentPlyPointer)&1;
	//
	// Right, we'll start by taking a look at the killer moves and then take a look at the rest of the
	// moves available
	//
	for( int index = -2; index < WIDTH; ++index )
	{
		if( index == -2 )
		{
			move = killerMoves[PRIMARY_KILLER_MOVE][level];
		}
		else if( index == -1 )
		{
			move = killerMoves[SECONDARY_KILLER_MOVE][level];
		}
		else 
		{
			move = searchPattern[ index ];
			//
			// Is this move one of the two killer moves we tested previously?
			//
			if( killerMoves[PRIMARY_KILLER_MOVE][level] == move || killerMoves[SECONDARY_KILLER_MOVE][level] == move)
			{
				//
				// Yes, check the next one
				//
				continue;
			}
		}
		
		if( lossOrWin[ move ] != 0 )
		{
			//std::cout << "Ignoring move " << move << " at depth: " << maxSearchDepth << " due to lossOrWin" << std::endl;
			continue;
		}
		 
		
		//
		// Let's generate a new board where we place a token in the specified column (move)
		//
		newBoard = newBoardAndMove( *bitboardArrayPointer[side], move );
		//
		// Was this a legal move or was the column full already?
		//
		if( !isLegal( newBoard ) )
		{
			//
			// We can't place a token in this column. Move on to the next column.
			//
			continue;
		}
		//
		// The move is legal. Let's make the move on the actual board.
		//
		makeMove(move);
		//
		// Now it's the min-player's turn
		//
		value = minValueIDKM( bitboardArrayPointer, currentPlyPointer, depthLimit - 1, expanded, INT_MIN, INT_MAX, abort, maxSearchDepth );
		//
		// Backtrack, take back the move we just played.
		//
		undoMove();
		//		std::cout << "\tcolumn: " << move << " Score: " << value << std::endl;
		//
		// Is this the best move yet?
		//
		
		if( value == INT_MAX || value == INT_MIN ) //We do not search win or loss moves any further, and do not add them to killer moves due to that
		{
			//std::cout << "Win or loss found, depth: " << maxSearchDepth << " move: " << move << " score: " << value << std::endl;
			lossOrWin[ move ] = value;
		}
		
		 
		if (value >= bestMoveValue)
		{
			bestMoveValue = value;
			bestMove = move;
		}
	}
	//
	// Return the best move (column) we found
	//
	return bestMove;	
}
//----------------------------------------------------------------------------------------------------------

int maxValueIDKM(  bitboard* bitboardArrayPointer[], int* currentPlyPointer, int depthLimit, int& expanded, int alpha, int beta, int& abort, int maxSearchDepth )
{
	//
	// The abort logic for the search thread
	//
	if( abort ) 
	{
		//		std::cerr << "Aborting search thread!!!  Time: " << getCurrTimeInMilliseconds() << "\n";
		pthread_exit( 0 );
	}
	//
	// Use the turn count (ply) to figure out which color/board Max has and which color Min has
	//
	int side = (*currentPlyPointer)&1;
	if( hasWon( *bitboardArrayPointer[((*currentPlyPointer)&1)^1] ) )
	{
		//
		// No point in going any further. Return the LOSS value.
		//
		return INT_MIN;
	}
	//
	// Have we reached the depth limit?
	//
	if( depthLimit <= 0 )
	{
		//
		// Evaluate the current board and return the value (score)
		//
		return ptr2UtilityFunction( bitboardArrayPointer, currentPlyPointer, side );
	}
	//
	// Increment the number of expanded nodes/states
	//
	++expanded;
	//
	// Declare and initialize variables
	//
	int v = INT_MIN;
	bitboard newBoard;
	int level = maxSearchDepth - depthLimit;
	int move;
	//
	// Iterate through the possible moves, starting with the two killer moves
	//
	for( int index = -2; index < WIDTH; ++index )
	{
		if( index == -2 )
		{
			move = killerMoves[PRIMARY_KILLER_MOVE][level];
		}
		else if( index == -1 )
		{
			move = killerMoves[SECONDARY_KILLER_MOVE][level];
		}
		else 
		{
			move = searchPattern[ index ];
			//
			// Is this move one of the two killer moves we tested previously?
			//
			if( killerMoves[PRIMARY_KILLER_MOVE][level] == move || killerMoves[SECONDARY_KILLER_MOVE][level] == move)
			{
				//
				// Yes, check the next one
				//
				continue;
			}
		}
		//
		// Let's generate a new board where we place a token in the current column
		//
		newBoard = newBoardAndMove( *bitboardArrayPointer[side], move );
		//
		// Was this a legal move or was the column full already?
		//
		if( !isLegal( newBoard ) )
		{
			//
			// We can't place a token in this column. Move on to the next column.
			//
			continue;
		}
		//
		// The move is legal. Let's make the move on the actual board.
		//
		makeMove(move);
		//
		// Now it's the min-player's turn
		//
		v = max( v, minValueIDKM( bitboardArrayPointer, currentPlyPointer, depthLimit-1, expanded, alpha, beta, abort, maxSearchDepth ) );
		//
		// Backtrack, take back the move we just played.
		//
		undoMove();
		//
		// Beta-pruning
		//
		if( v >= beta )
		{
			//
			// Set this as a killer move since it resulted in a cut-off. Then return the value/score.
			//
			setKillerMove(level, move);
			return v;
		}
		//
		// Update the alpha value
		//
		alpha = max( alpha, v );
	}
	//
	// Return the value of Max's best move
	//
	return v;
}
//----------------------------------------------------------------------------------------------------------

int minValueIDKM(  bitboard* bitboardArrayPointer[], int* currentPlyPointer,int depthLimit, int& expanded, int alpha, int beta, int& abort, int maxSearchDepth )
{	
	//
	// Use the turn count (ply) to figure out which color Max has and which color Min has
	//
	int side = (*currentPlyPointer)&1;
	//
	// Did the max-player win with the last move?
	//
	if( hasWon( *bitboardArrayPointer[((*currentPlyPointer)&1)^1] ) )
	{
		//
		// No point in going any further. Return the WIN value.
		//
		return INT_MAX;
	}
	//
	// Have we reached the depth limit?
	//
	if( depthLimit <= 0 )
	{
		//
		// Evaluate the current board and return the value (score)
		//
		return ptr2UtilityFunction( bitboardArrayPointer, currentPlyPointer,  side ); 
	}
	//
	// Increment the number of expanded nodes/states
	//
	++expanded;
	//
	// Declare and initialize variables
	//
	int v = INT_MAX;
	bitboard newBoard;
	int level = maxSearchDepth - depthLimit;
	int move;
	//
	// Iterate through the possible moves, starting with the two killer moves
	//
	for( int index = -2; index < WIDTH; ++index )
	{
		if( index == -2 )
		{
			move = killerMoves[PRIMARY_KILLER_MOVE][level];
		}
		else if( index == -1 )
		{
			move = killerMoves[SECONDARY_KILLER_MOVE][level];
		}
		else 
		{
			move = searchPattern[ index ];	
			//
			// Is this move one of the two killer moves we tested previously?
			//
			if( killerMoves[PRIMARY_KILLER_MOVE][level] == move || killerMoves[SECONDARY_KILLER_MOVE][level] == move)
			{
				//
				// Yes, check the next one
				//
				continue;
			}
		}
		//
		// Let's generate a new board where we place a token in the current column
		//
		newBoard = newBoardAndMove( *bitboardArrayPointer[side], move );
		//
		// Was this a legal move or was the column full already?
		//
		if( !isLegal( newBoard ) )
		{
			//
			// We can't place a token in this column. Move on to the next column.
			//
			continue;
		}
		//
		// The move is legal. Let's make the move on the actual board.
		//
		makeMove(move);
		//
		// Now it's the max-player's turn
		//
		v = min( v, maxValueIDKM( bitboardArrayPointer, currentPlyPointer, depthLimit-1, expanded, alpha, beta, abort, maxSearchDepth ) );
		//
		// Backtrack, take back the move we just played.
		//
		undoMove();
		//
		// Alpha-pruning
		//
		if( v <= alpha )
		{
			//
			// Set this as a killer move since it resulted in a cut-off and then return its value.
			//
			setKillerMove(level, move);
			return v;
		}
		//
		// Update the beta value
		//
		beta = min( beta, v );
	}
	//
	// Return the value of Min's best move
	//
	return v;	
}
//----------------------------------------------------------------------------------------------------------
